
# 判断一个数是否为素数函数
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        # 如果当前的数 i 能够整除给定的数 n，则 n 不是素数
        if n % i == 0:
            return False
    # 循环结束后没有找到能整除 n 的数，则说明 n 是素数
    return True

# 输出素数函数
def print_primes():
    count = 0
    # 遍历1~20000之间所有的数字
    for num in range(1, 20001):
        if is_prime(num):
            print(num, end=" ")
            count += 1
            # 5个为一行打印
            if count % 5 == 0:
                print()

print_primes()

# 最费时的函数是is_prime(n) 时间复杂度为O(n), 它使用了一个循环从2到n-1的遍历，对每一个数字都进行取余运算
# 优化时可以考虑只判断从2 到 sqrt(i) 是否存在能整除i的数，时间复杂度可以改进为O(sqrt(n))